//TIP 要<b>运行</b>代码，请按 <shortcut actionId="Run"/> 或
// 点击装订区域中的 <icon src="AllIcons.Actions.Execute"/> 图标。
public class Main {
    public static void main(String[] args) {

    }
    //给定一个单链表 L 的头节点 head ，单链表 L 表示为：
    //
    //L0 → L1 → … → Ln - 1 → Ln
    //请将其重新排列后变为：
    //
    //L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
    public void reorderList(ListNode head){
        if(head == null){
            return;
        }
        ListNode middle = middleList(head);
        ListNode cur2 = middle.next;
        middle.next = null;
        ListNode cur1 = head;
        cur2 = reverseList(cur2);
        mergeList(cur1,cur2);
    }
    public ListNode middleList(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public void mergeList(ListNode head1, ListNode head2) {
        ListNode temp1, temp2;
        while (head1 != null && head2 != null) {
            temp1 = head1.next; // 保存head1的下一个节点
            temp2 = head2.next; // 保存head2的下一个节点

            head1.next = head2; // head1连接到head2
            head2.next = temp1; // head2连接到原head1的下一个节点

            head1 = temp1; // 移动head1到下一个位置
            head2 = temp2; // 移动head2到下一个位置
        }
    }
    public ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}